package 中等.搜索.回溯;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/permutations-ii/
 */
public class 全排列II_47 {

    public static void main(String[] args) {

        System.out.println(new 全排列II_47().permuteUnique(new int[]{1, 1, 2}));

    }

    /**
     * 1，回溯，将最开始的状态看作 nums.length 个空白，每次从
     * nums 中选择一个从未被选择过的元素，放置到当前空白中，
     * 将全部空白填满则加入答案
     * 2，将原数组排序，保证第 idx 个回溯的过程中，每个数字只
     * 搜索一次，每次只搜索原数组相同数字的最后一个数字即可
     */
    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);

        List<List<Integer>> lists = new ArrayList<>();
        boolean[] visited = new boolean[nums.length];

        dfs(new ArrayList<>(), nums, visited, lists);

        return lists;
    }

    private void dfs(List<Integer> curList, int[] nums, boolean[] visited, List<List<Integer>> lists) {
        if (curList.size() == nums.length) {
            lists.add(new ArrayList<>(curList));
            return;
        }

        int idx = 0;
        while (idx < nums.length) {
            // 去重，取每个相同数字的最后一个未被选择过的元素
            // 当前元素选择过，也不能再选择
            while (idx < nums.length && visited[idx] ||
                    idx + 1 < nums.length && !visited[idx + 1] && nums[idx] == nums[idx + 1]) {
                idx++;
            }
            if (idx < nums.length) {
                visited[idx] = true;
                curList.add(nums[idx]);

                dfs(curList, nums, visited, lists);

                visited[idx] = false;
                curList.remove(curList.size() - 1);
            }
            idx++;
        }
    }

}
